import java.util.ArrayList;
import java.util.List;

public class BinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val){
            this.val = val;
        }
    }
    List<TreeNode> list = new ArrayList<>();

    public void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

    public List<TreeNode> preOrder2(TreeNode root){
        List<TreeNode> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        list.add(root);
        List<TreeNode> leftList = preOrder2(root.left);
        list.addAll(leftList);
        List<TreeNode> rightList = preOrder2(root.right);
        list.addAll(rightList);

        return list;
    }

    public void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    public void postOrder(TreeNode root){
        if(root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    public int size(TreeNode root){
        if(root == null){
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }

    public int getLeafSize(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafSize(root.left) + getLeafSize(root.right);
    }

    public int getKLevelNodeCount(TreeNode root, int k){
        if(root == null || k <= 0){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left, k - 1) +
                getKLevelNodeCount(root.right, k - 1);
    }

    public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int high = 1;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        high += leftHeight > rightHeight ? leftHeight : rightHeight;

        return high;
    }

    public TreeNode create(){
        TreeNode a = new TreeNode('A');
        TreeNode b = new TreeNode('B');
        TreeNode c = new TreeNode('C');
        TreeNode d = new TreeNode('D');
        TreeNode e = new TreeNode('E');
        TreeNode f = new TreeNode('F');
        TreeNode g = new TreeNode('G');
        TreeNode h = new TreeNode('H');

        a.left = b;
        b.left = d;
        b.right = e;
        e.right = h;
        a.right = c;
        c.left = f;
        c.right = g;

        return a;
    }
}
